#pragma once

#include "iostream"
#include "vector"
#include "algorithm"

using namespace std;

/*HJJ QQ479287006
 *
 * */
int coinChange(vector<int> &coins, int amount) {

    vector<int> dp(amount + 1, INT_MAX);
    //先物品

    dp[0] = 0;
    for (int i = 0; i < coins.size(); i++) {
        for (int j = 0; j <= amount; j++) {
            if ((j - coins[i] >= 0) && dp[j - coins[i] != INT_MAX])
                dp[j] = min(dp[j], dp[j - coins[i]] + 1);

        }

    }

    return dp[amount];
}